\documentclass[submission]{FPSAC2017}

\articlenumber{13}
\addbibresource{13_Bergeron_Benedetti.bib}

\usepackage{tikz}
\usepackage{color}
\newcommand{\blue}[1]{\textcolor{blue}{#1}}
\newcommand{\red}[1]{\textcolor{red}{#1}}
\newcommand{\green}[1]{\textcolor{green}{#1}}


\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{definition}
\newtheorem{example}[theorem]{Example} 
\newtheorem{remark}[theorem]{Remark} 
\newtheorem{definition}[theorem]{Definition} 


%-------------------------------------------------------------------
% MACROS
%-------------------------------------------------------------------

\def\Id{{\bf 1}}
\DeclareMathOperator{\coker}{coker}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\End}{End}

\def\llb{{[\![}}
\def\rrb{{]\!]}}


\newcommand{\abs}[1]{\lvert#1\rvert} %for absolute value
\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}} %for round matrix

\newcommand{\larc}[1]{\hspace{-.4ex}\overset{#1}{\frown}\hspace{-.4ex}}
\newcommand{\slarc}[1]{\overset{#1}{\frown}}

\newcommand{\gel}{>_{\ell}}
\newcommand{\lel}{<_{\ell}}

\newcommand{\one}{\mathbf{1}}
\newcommand{\euler}{\mathbf{e}}

\let\onto=\twoheadrightarrow
\let\into=\hookrightarrow
\let\map=\xrightarrow
\newcommand{\xyinc}{\ar@{^{(}->}}
\newcommand{\mapsby}[1]{ \overset{#1}{\longmapsto}}

\newcommand{\type}[2]{\mathsf T_{#1}(#2)}

\def\field{\Bbbk}
\newcommand{\Sr}{\mathrm{S}} %symmetric group

\newcommand{\rH}{\mathrm{H}}
\newcommand{\rL}{{\mathbf l}}
\newcommand{\rG}{{\mathbf g}}
\newcommand{\rD}{\mathrm{D}}

\newcommand{\bL}{\mathbf L}
\newcommand{\bE}{\mathbf E}
\newcommand{\bH}{\mathbf H}
\newcommand{\bh}{\mathbf h}
\newcommand{\bk}{\mathbf k}
\newcommand{\bK}{\mathbf K}
\newcommand{\bPi}{\mathbf \Pi}
\newcommand{\bG}{\mathbf{G}} 
\newcommand{\bp}{\mathbf p}
\newcommand{\bq}{\mathbf q}
\newcommand{\bmm}{\mathbf m}%\bm exists
\newcommand{\bd}{\mathbf d}

\newcommand{\Fc}{\mathcal{F}}
\newcommand{\Tc}{\mathcal{T}}
\newcommand{\Kc}{\mathcal{K}}
\newcommand{\Kcb}{\overline{\Kc}}

\newcommand{\Nb}{\mathbb{N}}
\newcommand{\Qb}{\mathbb{Q}}
\newcommand{\Cb}{\mathbb{C}}
\newcommand{\Zb}{\mathbb{Z}}
\newcommand{\Fb}{\mathbb{F}}
\newcommand{\Fq}{\Fb_q}

\newcommand{\Nf}{\mathfrak{n}}
\newcommand{\bNf}{\overline{\Nf}}
\newcommand{\Mf}{\mathfrak{m}}
\newcommand{\bMf}{\overline{\Mf}}

\newcommand{\GL}{\mathrm{GL}}
\newcommand{\Un}{\mathrm{U}}
\newcommand{\Mat}{\mathrm{M}}
\newcommand{\Tri}{\mathrm{T}}

\newcommand{\FC}{\bm{\mathrm{f}}}
\newcommand{\CF}{\bm{\mathrm{cf}}}
\newcommand{\SC}{\bm{\mathrm{scf}}}

\newcommand{\bdot}{\bm\cdot}

\newcommand{\qand}{\quad\text{and}\quad}
\newcommand{\qor}{\quad\text{or}\quad}
\newcommand{\qqand}{\qquad\text{and}\qquad}
\newcommand{\qqor}{\qquad\text{or}\qquad}

\newcommand{\caro}[1]{\todo[color=orange!30]{#1 \\ \hfill --- C.}}
\newcommand{\nantel}[1]{\todo[color=red!30]{#1 \\ \hfill --- N.}}
\setlength{\marginparwidth}{2cm}


\title[{A}ntipode for linearized Hopf monoid]{{T}he antipode of linearized Hopf monoids}

\author{Carolina Benedetti \and Nantel Bergeron\thanks{Bergeron supported in part by NSERC.}}


\address{Department of Mathematics and Statistics, York  University, Toronto, Ontario, Canada}

\received{\today}

\abstract{Many combinatorial Hopf algebras $H$ in the literature are the functorial image of a linearized Hopf monoid $\bH$. That is, $H=\Kc (\bH)$ or $H=\Kcb (\bH)$. For the functor $\Kc$,  the antipode of $\bH$ may not be preserved, but the Hopf monoid $\bL\times\bH$ gives $H=\Kc (\bH)=\Kcb(\bL\times\bH)$, and the functor $\Kcb$ preserves antipodes. In this paper, we give a cancelation free and multiplicity free formula for the antipode of $\bL\times\bH$. 
We also compute the antipode for $\bH$ when it is commutative and cocommutative. We get new formulas that are not always cancelation free but 
can be used to obtain one for $H$ in some cases.
The formulas for $\bH$ involve acyclic orientations of hypergraphs.
In an example, we introduce a chromatic invariant for the increasing sequences of a permutation and show that its evaluation at $t=-1$ relates to another statistic on permutations.
}

\keywords{Antipode, Hopf monoid, Hopf algebra} 

\begin{document}

\maketitle

%%%%%%%%%%%%%%
%% INTRODUCTION
%%%%%%%%%%%%%%
\section*{Introduction}



In recent literature, we see a wealth of  results with cancelation free formulas for antipode in various graded Hopf algebras \cite{Humpert-Martin, Benedetti-Sagan,Bergeron-Ceballos, Aguiar-Ardila}.  The interest of such formulas lies in their geometric interpretation (as in \cite{Aguiar-Ardila}) or to allow a structural understanding of the principal evaluation of the combinatorial invariants. One remarkable example of this is the proof of Humpert-Martin \cite{Humpert-Martin} of a theorem of Stanley.

The general principle is that antipode formulas give us interesting identities for the combinatorial invariants.
A theorem of \cite{ABS} gives us a canonical way of constructing combinatorial invariants with values in the space $QSym$ of quasisymmetric functions.
Given a combinatorial Hopf algebra $H=\bigoplus_{n\ge 0} H_n$ with multiplicative morphism $\zeta\colon H\to\field$
we have a unique Hopf morphism
  $\Psi:H\to QSym$
  such that $\zeta=\phi_1\circ\Psi$ where $\phi_1\big(f(x_1,x_2,\ldots)\big)=f(1,0,0,\ldots)$. Moreover, there is a Hopf
  morphism $\phi_t \colon QSym\to \field[t]$ given by 
   $\phi_t (M_a)={t \choose \ell(a)},$
   where $M_a$ is the monomial quasisymmetric function indexed by an integer composition $a=(a_1,a_2,\ldots,a_\ell)$ and $\ell(\alpha)=\ell$.
   
For $H$ the Hopf algebra of graphs, and $\zeta$ defined by
  $\zeta(G)=1$  if $G$ is discrete graph and $0$ otherwise \cite[Example 4.5]{ABS}, we have that $\chi_G(t)=\phi_t\circ \Psi(G)$ is the chromatic polynomial of $G$.
To understand Stanley's theorem about acyclic orientations of $G$ we remark that
the antipode of $\field[t]$ is given by $S\big(p(t)\big)=p(-t)$. So we have
  $\chi_G(-1)=\zeta\circ S(G).$
It is now clear that the result of Stanley follows from the cancelation free formula of the antipode on graphs as given by~\cite{Humpert-Martin,Aguiar-Ardila}.

Here, we  present a general framework that allows us to derive new formulas for the antipode of many of the graded Hopf algebras in the literature. 
To achieve this, we lift the structure of a graded Hopf algebra to 
a Hopf monoid in Joyal's category of species \cite{AM:2010}.
The few basic notions and examples needed for our purposes are reviewed in
\cref{s:hopf}.

The first goal of this paper is to construct a cancelation free and multiplicity free formula for
the antipode of the Hadamard product $\bL\times\bH$ of the Hopf monoids of linear order $\bL$ and a linearized Hopf monoid $\bH$. 
This surprising result will be done in \cref{s:antiLxH}. One interesting fact is that even if at the level of Hopf monoid the formula is cancelation free,
many cancelations remain when applying $\Kcb(\bL\times\bH)$.  Yet this gives us new formulas for the antipode and potentially new identities.
We discuss this in \cref{s:HopfAlgebras}. Here $\Kcb$ and 
$\Kc$ are the Fock functors that give graded 
Hopf algebras from Hopf monoids (see \cref{s:hopf}). 

In \cref{s:antiH}, we consider the antipode formula for a commutative and cocommutative linearized Hopf monoid $\bH$.
One consequence is that the most interesting case to consider is the Hopf monoid of hypergraph $\bf HG$ as defined in \cref{ss:hypergraph}.
The Hopf monoid $\bf HG$ contains all the information of the antipode for any other commutative and cocommutative linearized Hopf monoid $\bH$.
This is an interesting fact and we will show completely the relationship.
We give an antipode formula for $\bH$  in \cref{subsec:acyclic} related to orientation of hypergraphs.
We will derive an interesting identity using our new formulas for the antipode in \cref{ss:antiStan}.
In particular we introduce a chromatic polynomial for total orders (permutations) and show an analogue of Stanley's theorem in that case.

From this work we see that it is important to study the Hopf monoid $\bf HG$ as defined in \cref{ss:hypergraph}.
In future work, with John Machacek, we will show the geometric interpretation for the antipode of $\bf HG$ is encoded by a hypergraphical nestohedron. This is done in the spirit of the work in \cite{Aguiar-Ardila}.

%%%%%%%%%%%%%%
%% HOPF MONOID
%%%%%%%%%%%%%%
\section{Hopf monoids}\label{s:hopf}


We review basic notions on Hopf monoids. See \cite{AM:2010} for a deeper study on this topic. 
%%%%%%%%%%%%%%
%% Basic Definition of Hopf monoid
%%%%%%%%%%%%%%
A \emph{vector species} $\bH$ is a collection of vector spaces $\bH[I]$,
one for each finite set $I$, equivariant with respect to bijections $I\cong J$.
A morphism of species $f:\bH\to\bf Q$ is a collection of linear maps
$f_I:\bH[I]\to{\bf Q}[I]$ which commute with bijections.

A \emph{set composition} of a finite set $I$ is a finite sequence $(A_1,\ldots,A_k)$
of disjoint subsets of $I$ whose union is $I$. In this situation, we write
$
(A_1,\ldots,A_k)\models I.
$

A \emph{Hopf monoid} consists of a vector species $\bH$
equipped with two collections $\mu$ and $\Delta$ of linear maps
$\bH[A_1]\otimes\bH[A_2] \map{\mu_{A_1,A_2}}\bH[I]
\qand
\bH[I]\map{\Delta_{A_1,A_2}} \bH[A_1]\otimes\bH[A_2]$ subject to a number of standard axioms (associativity, unity, compatibility, etc).
The Hopf monoid $\bH$ is \emph{connected} if
 $\bH[\emptyset]=\field$.

The collection $\mu$ is the \emph{product} and the collection $\Delta$
is the \emph{coproduct} of the Hopf monoid $\bH$. For any Hopf monoid $\bH$ the existence
of the antipode map $S\colon \bH\to\bH$ is guaranteed and it can be computed using Takeuchi's formula as follows. For any finite set $I$
\begin{equation}\label{eq:takeuchi}
 S_I = \sum_{k=1}^{|I|}\sum_{(A_1,\ldots,A_k)\models I} (-1)^{k} \mu_{A_1,\ldots,A_k} \Delta_{A_1,\ldots,A_k}
 = \sum_{A\models I} (-1)^{\ell(A)} \mu_A \Delta_A\,.
\end{equation}
Here, for $k=1$, we have $\mu_{A_1}=\Delta_{A_1}=\Id_I$ the identity map on $\bH[I]$, and for $k>1$,
 $  \mu_{A_1,\ldots,A_k} = \mu_{A_1,I\setminus A_1}(\Id_{A_1}\otimes\mu_{A_2,\ldots,A_k})$ and
       $\Delta_{A_1,\ldots,A_k} =(\Id_{A_1}\otimes\Delta_{A_2,\ldots,A_k}) \Delta_{A_1,I\setminus A_1}.
 $

%%%%%%%%%%%%%%
%% HOPF MONOID of LINEAR ORDERs
%%%%%%%%%%%%%%
\begin{example}[Linear orders $\bL$]\label{ss:order}
For any finite set $I$ let
$\rL[I]$ be the set of all linear orders on $I$. For instance, if $I=\{a,b,c\}$,
$\rL[I]=\{abc,\,bac,\,acb,\,bca,\,cab,\,cba\}.$
The vector species $\bL$ is such that $\bL[I]:=\field\rL[I]$ is the vector space with basis $\rL[I]$. 

Let $(A_1,A_2)\models I$.
Given linear orders $\alpha_1\in\rL[A_1]$ and $\alpha_2\in\rL[A_2]$,
their concatenation $\alpha_1\cdot \alpha_2\in\rL[I]$. This is the linear order given by $\alpha_1$ followed by $\alpha_2$.
Given a linear order $\alpha$ on $I$ and $P\subseteq I$, the restriction 
 $\alpha|_P$ is the ordering in $P$ given by the order $\alpha$.
These operations give rise to maps
$(\alpha_1,\alpha_2) \mapsto \alpha_1\cdot\alpha_2$ and 
$ \alpha \mapsto (\alpha |_{A_1},\alpha |_{A_2})$.
Extending by linearity, we obtain linear maps
$ \mu_{A_1,A_2}:\bL[A_1]\otimes\bL[A_2] \to \bL[I]$ and $\Delta_{A_1,A_2}:\bL[I]\to \bL[A_1]\otimes\bL[A_2]$
which turn $\bL$ into a cocommutative but not commutative Hopf monoid.
\end{example}

%%%%%%%%%%%%%%
%% HOPF MONOID of GRAPHS
%%%%%%%%%%%%%%
\begin{example}[Graphs $\bG$]\label{ss:graph}
A \emph{(simple) graph} $g$ on a finite set $I$ is a collection $E$ of subsets of $I$ of size 2.
The elements of $I$ are the \emph{vertices} of $g$.
There is an \emph{edge} between two vertices $i, j$ if $\{i,j\}\in E$.
 Given a graph $g$ on $I$ and $P\subseteq I$, the restriction
$g|_P$ is the graph on the vertex set $P$ whose edges are the edges of $g$ between elements of $P$.
Let $(A_1, A_2)\models I$.
Given graphs $g_i$ of $A_i$, $i=1,2$, 
their union is the graph $g_1\cup g_2$ of $I$ 
whose edges are those of $g_1$ and those of $g_2$.

Let $\rG[I]$ denote the set of graphs on $I$ and $\bG[I]=\field \rG[I]$ the vector
space with basis $\rG[I]$. 
A Hopf monoid structure on $\bG$ is defined from $
(g_1,g_2) \mapsto g_1\cup g_2$
and $ g  \mapsto (g |_{A_1},g |_{A_2})$.
Extending by linearity, we obtain linear maps
$\mu_{A_1,A_2}:\bG[A_1]\otimes\bG[A_2] \to \bG[I]$ and
$\Delta_{A_1,A_2}:\bG[I]\to \bG[A_1]\otimes\bG[A_2]$.
These operations turn the species $\bG$ into a Hopf monoid that is both commutative and cocommutative.
\end{example}

%%%%%%%%%%%%%%
%% HOPF MONOID of HYPERGRAPHS
%%%%%%%%%%%%%%
\begin{example}[Hypergraphs $\bf HG$]\label{ss:hypergraph}
Let  $2^I$ denote the collection of subsets of $I$. Let $\bf HG[I]=\field {\bf hg}[I]$ be the space spanned by the basis $\bf hg[I]$ where
      ${\bf hg}[I]=\big\{h \subseteq 2^I\,:  U\in h$ implies $|U|\ge 2\big\}$
An element $h\in{\bf hg}[I]$ is a \emph{hypergraph on $I$}.
For $(P,T)\models I$ and $h,k\in {\bf hg}[I]$, the multiplication is given by $\mu_{P,T}(h,k)=h\cup k$ and the comultiplication 
is given by $\Delta_{P,T}(h) = h |_P\otimes h |_T$ where $h |_P=\{U\in h : U\cap P = U\}$. Extending these definitions linearly we have that $\bf HG$ is 
commutative and cocommutative Hopf monoid. 
\end{example}

%%%%%%%%%%%%%%
%% HADAMARD PRODUCT
%%%%%%%%%%%%%%
Given two species $\bH$ and $\bf Q$, their \emph{Hadamard product} is the species $\bH\times\bf Q$ defined by
$(\bH\times{\bf Q})[I] = \bH[I]\otimes{\bf Q}[I].$
If $\bH$ and $\bf Q$ are Hopf monoids, then so is $\bH\times\bf Q$, with the multiplication and comultiplication defined pointwise. 
%%%%%%%%%%%%%%
%% FUNCTOR K and Kbar
%%%%%%%%%%%%%%
As described in~\cite{AM:2010}, there are some interesting functors from the category of species to the category of graded vector spaces. Let $[n]:=\{1,2,\ldots,n\}$ and assume throughout that $\text{char}(\field)=0$. Given a species $\bH$, the symmetric group $S_n$ acts on $\bH[n]$ by relabelling. Define the functors $\Kc$ and $\Kcb$ by
  $ \Kc({\bf H}) = \bigoplus_{n\ge 0} {\bf H}[n]$
 and     $\Kcb({\bf H}) = \bigoplus_{n\ge 0} {\bf H}[n]_{S_n}$
 where ${\bf H}[n]_{S_n}={\bf H}[n]\big/ \langle x-{\bf H}[\sigma](x) \mid \ \sigma\in S_n; \ x\in {\bf H}[n]\rangle$
 denotes the quotient space of equivalence classes under the $S_n$ action. When $\bH$ is a Hopf monoid, 
  we can build a product and coproduct
on $ \Kc({\bf H})$ and $ \Kcb({\bf H})$ from those of $\bH$ together
with certain canonical transformations.

A very interesting relation between the functors $\Kc$ and $\Kcb$ is given in~\cite[Theorem~15.13]{AM:2010} as follows:
$ \Kcb(\bL\times\bH) \cong \Kc(\bH).$ In this paper we aim to make use of this relation to study the antipode problem for some Hopf algebras.


%%%%%%%%%%%%%%
%% linearized
%%%%%%%%%%%%%%
\smallskip
\noindent {\bf Linearized Hopf monoids:} A \emph{set species} $\bh$ is a collection of sets $\bh[I]$,
one for each finite set $I$, equivariant with respect to bijections $I\cong J$.
We say that $\bh$ is a basis for a Hopf monoid $\bH$ if for every finite set $I$ we have that $\bH[I]=\field \bh[I]$, the vector space with basis $\bh[I]$. We say that the monoid $\bH$ is \emph{linearized} in the basis $\bh$ if the product and coproduct maps have the following properties.
The product
$\mu_{A_1,A_2}: \bH[A_1] \otimes \bH[A_2] \to \bH[I]$ is the linearization of a map
$\bh[A_1] \otimes \bh[A_2] \to \bh[I] $ and the coproduct $\Delta_{A_1,A_2}: \bH[I]  \to \bH[A_1]\otimes\bH[A_2]$ is the linearization of a map
$ \bh[I]  \to (\bh[A_1]\otimes\bh[A_2])\cup\{0\}\,.$ From now on, we will use capital letters for vector species and lower case for set species.
The Hopf monoids $\bL$, $\bG$ and $\bf HG$ are linearized in the bases $\bf l$, $\bf g$ and $\bf hg$ respectively. 

%%%%%%%%%%%%%%
%% ANTIPODE FOR LxP
%%%%%%%%%%%%%%
\section{Antipode for linearized Hopf monoid $\bL\times \bH$}\label{s:antiLxH}

In this section we show a multiplicity free and cancelation free formula for the antipode of Hopf monoids of the form $\bL\times \bH$ where $\bH$ is linearized in some basis. 
%%%%%%%%%%%%%%
%% ANTIPODE FROM TAKEUCHI
%%%%%%%%%%%%%%
Let $\bH$ be a Hopf monoid linearized in the basis $\bh$. We intend to resolve the cancelations in the Takeuchi formula for $\bL\times\bH$. For a fixed finite set $I$ let $(\alpha,x)\in ({\bf l}\times\bh)[I]$, that is, $\alpha$ is a linear ordering on $I$ and $x$ is an element of $\bh [I]$. From~\eqref{eq:takeuchi} we have
\begin{equation}\label{eq:takeuchi1}
 S_I(\alpha,x) =  \sum_{A\models I} (-1)^{\ell(A)} \mu_A \Delta_A(\alpha,x)
  = \sum_{A\models I \atop \Delta_A(x)\ne 0} (-1)^{\ell(A)} (\alpha_A,x_A),
\end{equation}
 summing over all $A=(A_1,\ldots,A_k)\models I$, where $\alpha_A$ denotes the element in $\bf l [I]$ given 
  $\alpha_A= \alpha|_{A_1}\cdot  \alpha|_{A_2}\cdots \alpha_ \alpha|_{A_k}$ and if $\Delta_A(x)\ne 0$, then
  $x_A=\mu_A\Delta_A(x) \in \bh[I].$
Each composition $A$ gives rise to single elements $\alpha_A$ and $x_A$ since $\bL$ and $\bH$ are linearized in the basis $\bf l$ and $\bh$, respectively. 
We can thus rewrite~\eqref{eq:takeuchi1} as
\begin{equation}\label{eq:takeuchi2}
 S_I(\alpha,x) = \sum_{(\beta,y)\in ({\bf l}\times\bh)[I]}\Big(\sum_{A\models I \atop (\alpha_A,x_A)=(\beta,y)} (-1)^{\ell(A)}\Big) (\beta,y).
\end{equation}
Let 
 ${\mathcal C}_{\alpha,x}^{\beta,y}=\big\{A\models I : (\alpha_A,x_A)=(\beta,y)\big\}$.

\begin{theorem}\label{thm:antiLxP} Let $\bH$ be a linearized Hopf monoid in the basis $\bf h$. For $(\alpha, x)\in({\bf l}\times\bh)[I]$ we obtain
 \begin{equation}\label{eq:thm1}
 S_I(\alpha,x) = \sum_{(\beta,y)\in ({\bf l}\times\bh)[I]} c_{\alpha,x}^{\beta,y} \,(\beta,y),
\qquad\text{where}\qquad
  c_{\alpha,x}^{\beta,y}=\sum_{A\in {\mathcal C}_{\alpha,x}^{\beta,y}} (-1)^{\ell(A)}\in\{1,-1,0\}.
\end{equation}
\end{theorem}

The proof of this theorem and the following lemmas are given in our full paper~\cite{BB_full}. Here we sketch the main steps.
We make use of the refinement order on set compositions to show that the set ${\mathcal C}_{\alpha,x}^{\beta,y}$ has a unique minimum. 

%%%%%%%%%%%%%%
%%  REFINEMENT ORDER 
%%%%%%%%%%%%%%
\noindent {\bf Minimal element of ${\mathcal C}_{\alpha,x}^{\beta,y}$:}
Given $A=(A_1,\ldots,A_k)$ and $B=(B_1,\ldots,B_\ell)$ set compositions on a set $I$, 
we say that $A$ \emph{refines} $B$, and we write $A\le B$, if the parts of $B$ are union of consecutive parts of $A$. 
In what follows we will write $(2,57,3,9,68)$ instead of $\big(\{2\},\{5,7\},\{3\},\{9\},\{6,8\}\big)$. 
For example
$A = (2,57,3,9,68) \le (2357,689)$
but $A$ does not refine $(57,23,689)$. Denote by $(\mathcal P_I,\leq)$ the poset of set compositions of $I$, ordered by refinement.
Consider the order $\le$ restricted to the set ${\mathcal C}_{\alpha,x}^{\beta,y}$.

\begin{lemma}\label{le:min}
If ${\mathcal C}_{\alpha,x}^{\beta,y}\ne\emptyset$, then there is a unique minimal element in $({\mathcal C}_{\alpha,x}^{\beta,y},\le)$.
\end{lemma}

For the rest of this section, let $\alpha,\beta,x$ and $y$ be fixed and let $\Lambda=(\Lambda_1,\Lambda_2,\ldots,\Lambda_m)$ be the minimum of ${\mathcal C}_{\alpha,x}^{\beta,y}\ne \emptyset$.
For any $A\in{\mathcal C}_{\alpha,x}^{\beta,y}$ let $[\Lambda,A]$ denote the interval  $\big\{ B\models I : \Lambda\le B\le A\big\}\subseteq \mathcal P_I$. 

\begin{lemma}\label{le:lowerideal}
If ${\mathcal C}_{\alpha,x}^{\beta,y}\ne\emptyset$, then for any $A\in{\mathcal C}_{\alpha,x}^{\beta,y}$ we have that 
$[\Lambda,A]\subseteq {\mathcal C}_{\alpha,x}^{\beta,y}$.
\end{lemma}


\begin{lemma}\label{le:upperideal} For $ {\mathcal C}_{\alpha,x}^{\beta,y}\ne \emptyset$,
the minimal elements of $[\Lambda,(I)]\setminus {\mathcal C}_{\alpha,x}^{\beta,y}$ are all of the form\break
 $(\Lambda_1,\ldots,\Lambda_{i-1},\Lambda_i\cup\Lambda_{i+1}\cup\cdots\cup \Lambda_j,\Lambda_{j+1},\ldots,\Lambda_m)$
for some $1\le i<j\le m$.
\end{lemma}

%%%%%%%%%%%%%%
%% SIGN REVERSING INVOLUTION I
%%%%%%%%%%%%%%
\noindent {\bf Graph $G_{\alpha,x}^{\beta,y}$:}
Using \cref{le:upperideal} we define a graph $G_{\alpha,x}^{\beta,y}$ on the vertex set $[m]$ as follows. 
We have an edge $\{a,b\}\in G_{\alpha,x}^{\beta,y}$  for each minimal element of $[\Lambda,(I)]\backslash {\mathcal C}_{\alpha,x}^{\beta,y}$.
More precisely, $\{a,b\}$ is an edge in $ G_{\alpha,x}^{\beta,y}$ if for $1\le a<b\le m$ the following holds:


\noindent $\quad (1)\ $ For $B_{ab}=(\Lambda_1,\ldots,\Lambda_{a-1},\Lambda_a\cup\cdots\cup \Lambda_b,\Lambda_{b+1},\ldots,\Lambda_m)$ we have
  $ \alpha_{B_{ab}}\ne \beta$ or $x_{B_{ab}}\ne y.$
  
\noindent $\quad (2)\ $ For any $a<r<b$, we have $ \alpha_{B_{ar}}= \beta=\alpha_{B_{rb}}$ and $x_{B_{ar}}= y=x_{B_{rb}}.$

\noindent Condition (1), in particular guarantees that no element $A\in{\mathcal C}_{\alpha,x}^{\beta,y}$ induces an edge in $G_{\alpha,x}^{\beta,y}$. Condition (2) allows us to conclude that the graph $G$ is \emph{non-nested}: for any pair of edges $(a,b),(c,d)\in G$ such that $a\le c\le b$, it follows  $a<c\le b<d$

\begin{example}\label{ex:LxHgraph}
Consider the Hopf monoid of graphs $\bG$ as in \cref{ss:graph}.  $\bG$ is linearized in the basis $\bf g$.
Let $I= \{a,b,c,d,e,f,h\}$; $x,y\in{\bf g}[I]$ be the graphs \vskip -10pt
$$
x=
\begin{tikzpicture}[scale=.5,baseline=.5cm]
	\node (a) at (0,0) {$\scriptstyle a$};
	\node (b) at (1,.1) {$\scriptstyle f$};
	\node (c) at (2,0) {$\scriptstyle c$};
	\node (d) at (-.5,1) {$\scriptstyle d$};
	\node (e) at (.6,1.2) {$\scriptstyle e$};
	\node (h) at (0,2) {$\scriptstyle h$};
	\node (f) at (2.5,1.4) {$\scriptstyle b$};
	\draw (a) .. controls (1,-.5) ..   (c); 
	\draw (h) --   (f); 
	\draw (b) --   (.6,1); 
	\draw (d) --  (b); 
\end{tikzpicture} 
\qquad \qquad
y=
\begin{tikzpicture}[scale=.5,baseline=.5cm]
	\node (a) at (0,0) {$\scriptstyle a$};
	\node (b) at (1,.1) {$\scriptstyle f$};
	\node (c) at (2,0) {$\scriptstyle c$};
	\node (d) at (-.5,1) {$\scriptstyle d$};
	\node (e) at (.6,1.2) {$\scriptstyle e$};
	\node (h) at (0,2) {$\scriptstyle h$};
	\node (f) at (2.5,1.4) {$\scriptstyle b$};
	\draw (b) --  (.6,1); 
	\draw (d) --  (b); 
\end{tikzpicture} 
$$
and $\alpha,\beta$ be the orders $\alpha=abcdefh$ and $\beta=abdefhc$. The minimum element of ${\mathcal C}_{\alpha,x}^{\beta,y}$
is $\Lambda=(a,b,def,h,c)$. Since $\Lambda$ has $5$ parts, the graph $G_{\alpha,x}^{\beta,y}$ is built on the set $[5]$.
We have 
$G_{\alpha,x}^{\beta,y}=\{\{2,4\}, \{4,5\}\}$.
The edges $\{2,4\}$ since $ x_{B_{24}}\ne y$ and $\{4,5\}$ since  $ \alpha_{B_{45}}\ne \beta$. 
We identify the set compositions in the interval $[\Lambda,(I)]$ with the set compositions of the interval  $[(1,2,3,4,5),(12\cdots 5)]$. 
We can represent ${\mathcal C}_{\alpha,x}^{\beta,y}$ as the following poset:\vskip -5pt
$$
\begin{tikzpicture}[scale=1.3,baseline=.5cm]
	\node (0) at (0,0) {$\scriptscriptstyle 1,2,3,4,5$};
	\node (12) at (-2.5,.5) {$\scriptscriptstyle 12,3,4,5$};
	\node (23) at (-.5,.5) {$\scriptscriptstyle 1,23,4,5$};
	\node (34) at (1,.5) {$\scriptscriptstyle 1,2,34,5$};
	\node (45) at (2.5,.5) {$\scriptscriptstyle \red{\underline{1,2,3,45}}$};
	\draw (0) -- (12);
	\draw (0) -- (23);
	\draw (0) -- (34);
	\node (123) at (-2,1) {$\scriptscriptstyle 123,4,5$};
	\node (12_34) at (-.5,1) {$\scriptscriptstyle 12,34,5$};
	\node (234) at (2,1) {$\scriptscriptstyle \red{\underline{1,234,5}}$};
	\draw (12)--(123);
	\draw (12)--(12_34);
	\draw (23)--(123);
	\draw (34)--(12_34);
\end{tikzpicture} 
$$
where the set compositions in red are the minimal compositions {\bf not} in ${\mathcal C}_{\alpha,x}^{\beta,y}$.
\end{example}

\begin{remark}
As in the example above, for now on we will identify the set compositions in the interval $[\Lambda,(I)]$ with the set compositions of the interval  $[(1,2,\ldots,m),(12\cdots m)]$.
An element $A\in {\mathcal C}_{\alpha,x}^{\beta,y}$ is viewed as a set composition $A\models[m]$.
\end{remark}

In our full paper~\cite{BB_full}, we use the structure of the graph $G_{\alpha,x}^{\beta,y}$ to define a sign reversing involution on the set ${\mathcal C}_{\alpha,x}^{\beta,y}$ that has at most a single fixed point. 
This completes the sketch of our proof of \cref{thm:antiLxP}.

The structure of ${\mathcal C}_{\alpha,x}^{\beta,y}$ depends only on the structure of the graph $G_{\alpha,x}^{\beta,y}$, which as remarked earlier, is non-nested. For $G:=G_{\alpha,x}^{\beta,y}$ we let  ${\mathcal C}(G):= {\mathcal C}_{\alpha,x}^{\beta,y}$ and $c(G) := c_{\alpha,x}^{\beta,y}$. 

\begin{definition}\label{def:disconnected}
We say that $G$ is \emph{disconnected} if there exists a vertex $1\leq r<m$ such that there is no $\{a,b\}\in G$ with $a\in\{1,\dots ,r\}$ and $b\in\{r+1,\dots,m\}$.
\end{definition}

\begin{lemma}\label{le:disconnected}
 If $G$ is disconnected, then $c(G)=0$.
\end{lemma}

\begin{lemma}\label{le:shortedge}
 If $\{i,i+1\}\in G$ for some $1\le i<m$, then 
  $ c(G)= c(G|_{\{1,\ldots, i\}})\cdot c(G|_{\{i+1,\ldots, m\}}) $.
\end{lemma}

%%%%%%%%%%%%%%
%% ANTIPODE FOR H commutative
%%%%%%%%%%%%%%
\section{Antipode for commutative linearized Hopf monoid $\bf H$}\label{s:antiH}

In this section we show new formulas for commutative and cocommutative linearized Hopf monoid $\bH$. 
We also aim to introduce a geometrical interpretation related to our antipode formula in terms of certain faces of a polytope in the spirit of the work of Aguiar-Ardila~\cite{Aguiar-Ardila}.
To achieve this, first we give a formula for the antipode in terms of orientations in hypergraphs as in \cref{subsec:acyclic}.
The second part will be done jointly with J. Machacek in a sequel paper and is previewed in \cref{ss:nestohedron}.

\vspace{3pt}
%%%%%%%%%%%%%%
%% ANTIPODE for H FROM TAKEUCHI
%%%%%%%%%%%%%%
\noindent {\bf Takeuchi's Formula for $\bH$:}
Let $\bH$ be a Hopf monoid linearized in the basis $\bh$. 
Again, we intend to resolve the cancelation in the Takeuchi formula for $\bH$. For a fixed finite set $I$ let $x\in \bh[I]$. 
From~\eqref{eq:takeuchi} we have
\begin{equation}\label{eq:takeuchiH1}
 S_I(x) =  \sum_{A\models I} (-1)^{\ell(A)} \mu_A \Delta_A(x)
  = \sum_{A\models I \atop \Delta_A(x)\ne 0} (-1)^{\ell(A)} x_A,
\end{equation}
 where for $(A_1,\ldots,A_k)\models I$  
and $\Delta_A(x)\ne 0$ we write $x_A=\mu_A\Delta_A(x) \in \bh[I].$
These are unique elements since $\bH$ is linearized in the basis $\bh$. 
We now let
 ${\mathcal C}_{x}^{y}=\big\{A\models I : x_A=y\big\}.$

  \begingroup\emergencystretch=10em
So far we have not considered any commutative property of $\bf H$. In general we have no control on the set ${\mathcal C}_{x}^{y}$, but when $\bf H$ is commutative and cocommutative,
it is tractable.
Given $x,y\in \bh[I]$ such that ${\mathcal C}_{x}^{y}\ne \emptyset$, choose a fixed minimal element $\Lambda=(\Lambda_1,\Lambda_2,\ldots,\Lambda_m)$  in ${\mathcal C}_{x}^{y}$ under refinement. We will see in \cref{lem:minimalcom} that $\Lambda$ is unique up to permutation of its parts. 
We  define a  simple hypergraph $G_x^y$ on the vertex set $[m]$ 
where $U\subseteq [m]$ is a hyperedge of $G_x^y$ if and only if
  \begin{equation}\label{eq:Gcom}
      \prod_{i\in U} x_{\Lambda_i} \ne x_{\cup_{i\in U} \Lambda_i}
  \qquad \text{ \bf and }\qquad \forall(P\subset U)\quad \prod_{i\in P} x_{\Lambda_i} = x_{\cup_{i\in P} \Lambda_i}.
  \end{equation}
Up to a reordering of the vertices $\{1,2,\ldots,m\}$, commutativity, cocommutativity and \cref{lem:minimalcom}  guarantee that $G_x^y$ is well defined and does not depend on our choice of $\Lambda$.
\endgroup

\begin{theorem}\label{thm:antiH} Under the conditions above 
 \begin{equation}\label{eq:thm2}
 S_I(x) = \sum_{y\in \bh[I]} a(G_x^y) y,
\end{equation}
where $a(G_x^y)$,  defined in \cref{subsec:acyclic}, is a signed sum of acyclic orientations of the hypergraph $G_x^y$.
\end{theorem}

\begin{remark}
If $G_x^y$ is a graph, that is, any hyperedge $U\in G_x^y$ is such that $|U|=2$, then every acyclic orientation will have the same sign. Hence the theorem above gives a
cancelation free formula for the antipode as shown in \cite{Humpert-Martin}. In general it will not be cancelation free but it is the best generalization, to our knowledge,
for hypergraphs and to a large class of Hopf monoids and Hopf algebras. \end{remark}

%%%%%%%%%%%%%%
%% Structure of C_x^y and its hypergraph
%%%%%%%%%%%%%%
\noindent{\bf Structure of ${\mathcal C}_{x}^{y}$ and its hypergraph $G_x^y$:}
We  establish some properties of ${\mathcal C}_{x}^{y}=\big\{A\models I : x_A=y\big\}$. This will allow us to determine the coefficient of $y$ in $S(x)$ given by
$c_x^y=\sum_{A\in {\mathcal C}_{x}^{y}} (-1)^{\ell(A)}$.

\begin{lemma}\label{lem:minimalcom}
 If $A$ and $\Lambda$ in $ {\mathcal C}_{x}^{y}$ are two minimal set compositions under refinement, then $A$ is a permutation of the parts of $\Lambda$.
 Conversely, any set composition obtained by a permutation of the parts of $\Lambda$ belongs to ${\mathcal C}_{x}^{y}$ and is minimal.
\end{lemma}


\begin{lemma}\label{le:Hlowerideal}
If ${\mathcal C}_{x}^{y}\ne\emptyset$, then for any $A\in{\mathcal C}_{x}^{y}$ and $\Lambda\in{\mathcal C}_{x}^{y}$ minimal, we have that 
$[\Lambda,A]\subseteq {\mathcal C}_{x}^{y}$.
\end{lemma}


\begin{lemma}\label{le:Hupperideal}
The minimal elements of $\big(\bigcup_{\sigma\in S_m} [\sigma\Lambda,(I)]\big)\setminus {\mathcal C}_{x}^{y}$ are all the  permutations of set compositions of the form
 $(\bigcup_{i\in U} \Lambda_i,\Lambda_{v_1},\Lambda_{v_2},\ldots,\Lambda_{v_r})$
for some $U\in\{1,2,\ldots,m\}$, where $r=m-|U|$ and $\{v_1,\ldots,v_r\}=I\setminus U$. 
\end{lemma}

This defines the hypergraph $G_x^y$ associated with ${\mathcal C}_{x}^{y}$. For fixed $x$ and $y$, \cref{le:Hupperideal} gives us a set of subsets $U\subseteq I$ defining ${\mathcal C}_{x}^{y}$.
  $G_x^y=\{U\subseteq I : \text{ $U$ minimal, } \prod_{i\in U} x_{\Lambda_i} \ne x_{\bigcup_{i\in U} \Lambda_i}\}$.
The hypergraph $G_x^y$ is as defined in~\eqref{eq:Gcom}.

\begin{example}\label{ex:hypergraph}
Let $\bf HG$ be as in \cref{ss:hypergraph}. Consider $I= \{a,b,c,d,e\}$ and pick $x=\big\{\{b,c\},\{a,b,e\},\{a,d,e\},\{b,c,e\}\big\}$ and $y=\big\{
\{b,c\}\big\}$ in ${\bf hg}[I]$. We can represent $x$ and $y$ as follows:
$$
x=
\begin{tikzpicture}[scale=.5,baseline=.3cm]
	\node (a) at (0,0) {$\scriptstyle a$};
	\node (b) at (1,.1) {$\scriptstyle b$};
	\node (c) at (2,0) {$\scriptstyle c$};
	\node (d) at (-.5,1) {$\scriptstyle d$};
	\node (e) at (.6,1.2) {$\scriptstyle e$};
	\draw [fill=gray] (.1,.1) .. controls (.5,.3) .. (.9,.2) .. controls (.65,.6) .. (.6,1) .. controls (.5,.5) .. (.1,.1) ; 
	\draw [fill=gray] (0,.15) .. controls (-.05,.6) .. (-.35,1) .. controls (.1,.8) .. (.5,1) .. controls (.1,.6) .. (0,.15) ; 
	\draw [fill=gray] (1.8,.1) .. controls (1.5,.2) .. (1.1,.2) .. controls (1.1,.5) .. (.7,1) .. controls (1.4,.3) .. (1.8,.1) ; 
	\draw (1.2,.1) .. controls (1.5,-.2) ..   (1.8,0); 
\end{tikzpicture} 
\qquad \qquad
y=
\begin{tikzpicture}[scale=.5,baseline=.3cm]
	\node (a) at (0,0) {$\scriptstyle a$};
	\node (b) at (1,.1) {$\scriptstyle b$};
	\node (c) at (2,0) {$\scriptstyle c$};
	\node (d) at (-.5,1) {$\scriptstyle d$};
	\node (e) at (.6,1.2) {$\scriptstyle e$};
	\draw (1.2,.1) .. controls (1.5,-.2) ..   (1.8,0); 
\end{tikzpicture} 
$$
Up to permutation, the minimum refinement of ${\mathcal C}_x^y$
is $\Lambda=(a,bc,d,e)$. Since $\Lambda$ has $4$ parts, the hypergraph $G_x^y$ is build on the set $\{1,2,3,4\}$.
We have that $x_{bc}x_{e}\ne x_{bce}$ and $x_{a}x_dx_e\ne x_{ade}$. Those are the only minimal coarsening of parts of $\Lambda$ that yield
such inequalities. Hence $G_x^y=\big\{\{1,3,4\},\{2,4\}\big\}$. We now identify the set compositions in  $\bigcup_{\sigma\in S_m} [\sigma\Lambda,(I)]$ with the set compositions in $\bigcup_{\sigma\in S_m}[(\sigma(1),\ldots,\sigma(m)),(12\cdots m)]$. There are $4!$ minimal elements with four parts. There are 30 compositions with 3 parts, namely all the permutations of $(12,3,4),(13,2,4)$, $(14,2,3)$, $ (23,1,4),(34,1,2)$.
We have removed here all the permutations of $\red{\underline{(24,1,3)}}$ and above. With 2 parts we have all the  permutations of $(123,4), (12,34),(14,23)$ for a total of 6. We have removed the permutations of 
$\red{\underline{(134,2)}}$.  Here
  $c_x^y=24-30+6=0$
\end{example}

The identification between $\bigcup_{\sigma\in S_m} [\sigma\Lambda,(I)]$ with $\bigcup_{\sigma\in S_m}[(\sigma(1),\ldots,\sigma(m)),(12\cdots m)]$\break shows that computing $c_x^y$ is equivalent 
to computing the coefficient of $\epsilon$, the hypergraph on $[m]$ with no edges, in the antipode of $G_x^y$ in the Hopf monoid of hypergraphs. This implies the following theorem:
\begin{theorem}\label{thm:hyper}
  Given a commutative and cocommutative linearized Hopf monoid {\bf H}, let $x,y\in {\bf h}[I]$. We have  
    $ c_x^y = c_{x/y}^\epsilon $
     where $\epsilon$ is the hypergraph on $[m]$ with no edges and $x/y=G_x^y$ is the hypergraph given in~\eqref{eq:Gcom}.
\end{theorem}



%%%%%%%%%%%%%%
%% Acyclic orientation of Hypergraphs
%%%%%%%%%%%%%%
\subsection{$c_x^y$ as a signed sum of acyclic orientations of simple hypergraphs}\label{subsec:acyclic} 
Recall that $G_x^y$ is a hypergraph on the vertices $\{1,2,\cdots,m\}$ as defined in~\eqref{eq:Gcom}. The ordering of $\{1,2,\cdots,m\}$ depends on a fixed choice of minimal element in ${\mathcal C}_x^y$.

\begin{definition}[Orientation and head] Given a hypergraph $G$ an {\sl orientation} $(\mathfrak{a},\mathfrak{b})$ of a hyperedge $U\in G$ is a choice of two nonempty subsets $\mathfrak{a},\mathfrak{b}$ of $U$ such that $U=\mathfrak{a}\cup\mathfrak{b}$ and $\mathfrak{a}\cap\mathfrak{b}=\emptyset$. We say that $\mathfrak{a}$ is the {\sl head} of the orientation $\mathfrak{a}\rightarrow\mathfrak{b}$ of $U$. 
 In general if $|U|=n$, then there are a total of $2^{n}-2$ possible orientations. An  {\sl orientation} of $G$ is an orientation of all the hyperedges of $G$. Given an orientation ${\mathcal O}$  on $G$, we say that $(\mathfrak{a},\mathfrak{b})\in{\mathcal O}$ if it is the orientation of an hyperedge $U=\mathfrak{a}\cup \mathfrak{b}$ in $G$.
\end{definition}

\begin{definition}[Acyclic orientation] Let $G$ be a hypergraph on the vertex set $V$.
Given an orientation $\mathcal O$ of $G$, we construct an oriented graph $G/{\mathcal O}$ as follow. 
We let $V/{\mathcal O}$ be the finest equivalence class of elements of $V$ defines by the heads of $\mathcal O$.
That is the equivalence defined by the transitive closure of the relation $a\sim  b$ if $a,b\in \mathfrak{a}$ for some head $\mathfrak{a}$ of $\mathcal O$.
The oriented edges $([a],[b])$ belong to $G/{\mathcal O}$ for equivalence classes $[a],[b]\in V/{\mathcal O}$  if and only if there is an oriented hyperedge $(\mathfrak{a},\mathfrak{b})$ of $\mathcal O$ such that $a\in \mathfrak{a}$ and $b\in \mathfrak{b}$. An orientation $\mathcal O$ of $G$ is {\sl acyclic} if the oriented graph $G/{\mathcal O}$ has no cycles.
\end{definition}

\begin{example}\label{ex:124_234}
 Let $G=\big\{\{1,2,4\},\{2,3,4\}\big\}$ be a hypergraph on the vertex set $V=\{1,2,3,4\}$. There are $(2^3-2)(2^3-2)=36$ possible orientations of $G$. The orientation ${\mathcal O}=\big\{ (\{4\},\{1,2\}),(\{2,4\},\{3\})\big\}$ is not acyclic. To see this, the set $V/{\mathcal O}=\{\{1\},\{2,4\},\{3\}\}$ and the oriented graph $G/{\mathcal O}$ contain the 1-cycle $([4],[2])$.
Similarly the orientation ${\mathcal O}'=\big\{ (\{4\},\{1,2\}),(\{2,3\},\{4\})\big\}$ is not acyclic. The equivalence set $V/{\mathcal O'}=\{\{1\},\{2,3\},\{4\}\}$ and the oriented graph $G/{\mathcal O'}$ contains the 2-cycle $([4],[2]);([2],[4])$.
There are 20  acyclic orientations and $\{ (\{4\},\{1,2\}),(\{4\},\{2,3\})\}$ is one example.
\end{example}

Let ${\mathfrak O}_x^y$ be the set of acyclic orientations of $G_x^y$. 
For any  $1\le i\le\ell$, let $A_{i,\ell}=A_i\cup A_{i+1}\cup\cdots\cup A_\ell$ and let $G/\mathcal{O}_{i,\ell}$ be the restriction of  $G/\mathcal{O}$ to the set $A_{i,\ell}$.


\begin{lemma}\label{lem:Omega}
For $x,y\in {\bf h}[I]$, consider the hypergraph $G_x^y$ on $V=\{1,2,\ldots,m\}$. There is a surjective map $\Omega\colon  {\mathcal C}_{x}^{y} \to {\mathfrak O}_x^y$. More precisely,
\begin{enumerate}
 \item[(a)] For any $A=(A_1,A_2,\ldots, A_\ell)\in {\mathcal C}_{x}^{y}$ there is a unique  $\Omega(A)\in {\mathfrak O}_x^y$ such that for $U\in G_x^y$ the orientation of $U$ is given by $(U\cap A_i,U\setminus A_i)$ where
  $i=\min\{j: A_j\cap U\ne \emptyset\}.$ Furthermore $V/{\Omega(A)}$ is a refinement of $\{A_1,A_2,\ldots,A_\ell\}$.
 \item[(b)] 
 For any  $\mathcal O\in {\mathfrak O}_x^y$, there is a unique  $A_{\mathcal O}=(A_1,A_2,\ldots, A_\ell)\in {\mathcal C}_{x}^{y}$ such that $V/{\mathcal O}=\{A_1,A_2,\ldots, A_\ell\}$ and $A_i$ is the unique source of the restriction  $G/\mathcal{O}_{i,\ell}$  where $\min(A_i)$ is maximal among the sources of $G/\mathcal{O}_{i,\ell}$.
We have that $\Omega(A_{\mathcal O})=\mathcal O$.
\end{enumerate}
\end{lemma}

\begin{theorem} \label{thm:anticoco}
For any $x,y\in {\bf h}[I]$ such that ${\mathcal C}_{x}^{y}\ne\emptyset$ we have
  $c_x^y=\sum_{{\mathcal O} \in {\mathfrak O}_x^y} (-1)^{\ell{(A_{\mathcal O}})} $.
\end{theorem}


\begin{example}
 Let $x=\big\{\{1,2,4\},\{2,3,4\}\big\}$ be a hypergraph on the vertices $\{1,2,3,4\}$.
  A full computation of the antipode gives us \vskip -7pt
    $$S(
\begin{tikzpicture}[scale=.5,baseline=.2cm]
	\node (a) at (0,0) {$\scriptstyle 2$};
	\node (b) at (1,.1) {$\scriptstyle 1$};
	\node (d) at (-.5,1) {$\scriptstyle 3$};
	\node (e) at (.6,1.2) {$\scriptstyle 4$};
	\draw [fill=gray] (.1,.1) .. controls (.5,.3) .. (.9,.2) .. controls (.65,.6) .. (.6,1) .. controls (.5,.5) .. (.1,.1) ; 
	\draw [fill=gray] (0,.15) .. controls (-.05,.6) .. (-.35,1) .. controls (.1,.8) .. (.5,1) .. controls (.1,.6) .. (0,.15) ; 
\end{tikzpicture} 
)= - \begin{tikzpicture}[scale=.5,baseline=.2cm]
	\node (a) at (0,0) {$\scriptstyle 2$};
	\node (b) at (1,.1) {$\scriptstyle 1$};
	\node (d) at (-.5,1) {$\scriptstyle 3$};
	\node (e) at (.6,1.2) {$\scriptstyle 4$};
	\draw [fill=gray] (.1,.1) .. controls (.5,.3) .. (.9,.2) .. controls (.65,.6) .. (.6,1) .. controls (.5,.5) .. (.1,.1) ; 
	\draw [fill=gray] (0,.15) .. controls (-.05,.6) .. (-.35,1) .. controls (.1,.8) .. (.5,1) .. controls (.1,.6) .. (0,.15) ; 
\end{tikzpicture} 
+2\  \begin{tikzpicture}[scale=.5,baseline=.2cm]
	\node (a) at (0,0) {$\scriptstyle 2$};
	\node (b) at (1,.1) {$\scriptstyle 1$};
	\node (d) at (-.5,1) {$\scriptstyle 3$};
	\node (e) at (.6,1.2) {$\scriptstyle 4$};
	\draw [fill=gray] (0,.15) .. controls (-.05,.6) .. (-.35,1) .. controls (.1,.8) .. (.5,1) .. controls (.1,.6) .. (0,.15) ; 
\end{tikzpicture} 
+2\ \begin{tikzpicture}[scale=.5,baseline=.2cm]
	\node (a) at (0,0) {$\scriptstyle 2$};
	\node (b) at (1,.1) {$\scriptstyle 1$};
	\node (d) at (-.5,1) {$\scriptstyle 3$};
	\node (e) at (.6,1.2) {$\scriptstyle 4$};
	\draw [fill=gray] (.1,.1) .. controls (.5,.3) .. (.9,.2) .. controls (.65,.6) .. (.6,1) .. controls (.5,.5) .. (.1,.1) ; 
\end{tikzpicture} 
-2\ \begin{tikzpicture}[scale=.5,baseline=.2cm]
	\node (a) at (0,0) {$\scriptstyle 2$};
	\node (b) at (1,.1) {$\scriptstyle 1$};
	\node (d) at (-.5,1) {$\scriptstyle 3$};
	\node (e) at (.6,1.2) {$\scriptstyle 4$};
\end{tikzpicture} 
$$
Using \cref{thm:antiH} we now need to use all 20 acyclic orientations of \cref{ex:124_234}.
\cref{lem:Omega}~(b) gives us the following 20 set compositions
$(4,3,2,1);$ $(3,4,2,1);$ $ (34,2,1);$ $ (3,2,4,1);$ $
 (2,4,3,1);$ $(23,4,1);$ $ (1,4,3,2);$ $ (3,1,4,2);$ $ (1,2,4,3);$ $ (1,23,4);$ $
 (1,24,3);$ $ (1,34,2);$ $
(3,12,4);$ $ (12,4,3);$ $ (123,4);$ $ (14,3,2);$ $ (3,14,2);$ $ (134,2);$ $ (3,24,1);$ $ (24,3,1).
$
There are $9$ even length set compositions in this list and $11$ odd length. The coefficient is indeed $9-11=-2$.
For the coefficient of $x$ in $S(x)$, we remark that $x/x$ is a single point with no edge. There is a unique orientation of $x/x$ 
and it is represented by a set composition with a single part. Thus the coefficient is $-1$. For $y=\big\{\{1,2,4\}\big\}$,
$x/y$ is a graph on two vertices with a single edge between the vertices. There are two orientations of such graph and each orientation is 
represented with a set composition having two parts. Hence the coefficient is $2$. The same argument applies for $y'=\big\{\{2,3,4\}\big\}$.
\end{example}



%%%%%%%%%%%%%%
%% Applications ???
%%%%%%%%%%%%%%
\section{Applications with Hopf algebras}\label{s:HopfAlgebras}

%%%%%%%%%%%%%%
%% Our formula for LxH in K(LxH)
%%%%%%%%%%%%%%
We have that $\Kcb(\bL\times\bH) \cong \Kc(\bH)$. Given $(\alpha,x)\in (\bL\times\bH)[n]_{S_n}$, the isomorphism is explicitly given by the map $(\alpha,x)\mapsto \bH[\alpha^{-1}](x)$ where $\alpha^{-1}\colon[n]\to[n]$
is the unique bijection such that $\alpha^{-1}(\alpha)=12\cdots n$ and $\bH[\alpha^{-1}]\colon \bH[n]\to\bH[n]$ is obtained via the functor $\bH$.
\cref{thm:antiLxP} gives us the following formula. For $x\in \bH[n]$
 \begin{equation}\label{eq:SforKH}
   S(x)= \sum_{(\beta,y)\in ({\bf l}\times\bh)[n]} c_{12\cdots n,x}^{\beta,y} \bH[\beta^{-1}](y) = \sum_{z\in\bh[n]}\Big( \sum_{\beta\in {\bf l}[n]}  c_{12\cdots n,x}^{\beta, \bH[\beta](z)} \Big) z\,.
 \end{equation}
Here we have identified the linear order $\beta\in{\bf l}[n]$ and the bijection $\beta=(\beta^{-1})^{-1}\colon[n]\to[n]$ in the notation $\bH[\beta](z)$. From \cref{thm:antiLxP}
we have obtained that the $c_{12\cdots n,x}^{\beta, \bH[\beta](z)}$ are $\pm 1$, but further cancelation may occur in~\eqref{eq:SforKH}. It is not the best formula in most cases but it is an improvement on Takeushi's formula. In the cases of graphs for the monoid $\bf G$ with basis $\bf g$ it is not cancelation free, but in some other examples it could be quite useful.


\begin{example} \label{ex:PR}
Consider now the Hopf monoid $\bL$ in \cref{ss:order}.  The Hopf algebra $PR=\Kc(\bL)$ was introduced by Patras-Reutenauer~\cite{PR:2004} 
and is also studied in~\cite{AM:2010}.
 \begin{theorem}  \label{thm:AntipodePR}
 For the Hopf algebra $PR$ and $\alpha\in{\bf l}[n]$
     $S(\alpha)=\sum_{\gamma\in{\bf l}[n]}(-1)^{m}  d_{\alpha,\gamma}\,\, \gamma\,$
     where $m=\ell\big( \epsilon\lor\gamma\big)$ and  $d_{\alpha,\gamma}$ is the number of  $\beta\in{\bf l}[n]$ such that for $\Lambda=\beta\lor(\beta\circ\gamma)$ we have
 $\beta$ is increasing with respect to $\epsilon$ within each part of $\Lambda$,
 $\beta\circ\gamma$  is  increasing  with respect to $\alpha$ within each part of $\Lambda$, and
$\max_\epsilon(\Lambda_i)>_\epsilon\min_\epsilon(\Lambda_{i+1})$ or $\max_\alpha(\Lambda_i)>_\alpha \min_\alpha(\Lambda_{i+1})$ for all $1\le i<m$.
 \end{theorem}
\end{example}

%%%%%%%%%%%%%%
%% Some Stanley like formula for other Hopf algebra
%%%%%%%%%%%%%%
\subsection{Using the antipode formula to derive new identities}\label{ss:antiStan} Any multiplicative  $\zeta\colon H\to\field$
gives rise to combinatorial invariant $\chi=\phi_t\circ \Psi$.

\begin{example} Consider $PR=\Kc({\bf L})$ as studied in \cref{ex:PR} and let $\zeta(x)=1$ if $x=\epsilon$, zero otherwise.
In this case $\zeta$ is multiplicative. $PR$ is cocommutative, hence $\Psi\colon PR\to QSym$ is a symmetric function (see~\cite{ABS}). 
Here for $\alpha\in{\bf l}[n]$ we have
   $ \Psi(\alpha)=\sum_{a\models n} c_a(\alpha) M_a,$
where $a=(a_1,\ldots,a_\ell)\models n$ is an integer composition of $n$, and $c_a(\alpha)$ is the number of ways to decompose $\alpha$ into increasing subsequences of type $a$.
More precisely
  $$c_a(\alpha)=\big|\{ A\models [n] :  \text{for } 1\le i\le \ell,\  |A_i|=a_i \text{ and }\alpha|_{A_i} \text{ is increasing}\}\big|.$$

The {\sl chromatic} polynomial $\chi_\alpha(t)$ is then
     $ \chi_\alpha(t)=\sum_{a\models n} c_a(\alpha) {t \choose \ell(a)}.$
 This polynomial, when evaluated at $t=m$ counts the number of ways to color the entries of $\alpha$ with at most $m$ distinct colors such that $\alpha$ restricted to a single color is increasing.
 Using \cref{thm:AntipodePR} we get the identity
 \begin{equation}\label{eq:PRidentity}
     \sum_{a\models n} (-1)^{\ell(\alpha)}c_a(\alpha) =\chi_\alpha(-1)=\zeta\circ S(\alpha) = (-1)^n d_{\alpha,\epsilon}.
     \end{equation}
For any $\beta\in{\bf l}[n]$ and $\gamma=\epsilon$ in \cref{thm:AntipodePR}, we have $\Lambda=\beta$ and 
     $$d_{\alpha,\epsilon}=\big|\{\beta\in {\bf l}[n] : \beta_i>\beta_{i+1}\text{ or }\alpha^{-1}(\beta_i)>\alpha^{-1}(\beta_{i+1})\}\big|.$$
     The identity~\eqref{eq:PRidentity} relates combinatorial invariants for permutations that look \emph{a priori} unrelated. 
 \end{example}

\begin{remark} To any $\alpha\in{\bf l}[n]$, one may associate a partial order $P_\alpha$ where $\alpha_i\prec \alpha_j$ if $i<j$ and $\alpha_i>\alpha_j$. 
Let $G_\alpha$  be the  incomparable graph associated to $P_\alpha$ (see \cite{stanley}). 
The symmetric function $\Psi(\alpha)$ above is in fact the Stanley's chromatic symmetric function of  $G_\alpha$.
\end{remark}


\begin{example} Let us consider the case where $\zeta_{21}\colon PR\to\field$ defined by $\zeta_{21}(x)=1$ if $x=2143\ldots(2n)(2n-1)$, zero otherwise.
This defines a symmetric function $\Psi_{21}\colon PR\to QSym$. 
Here for $\alpha\in{\bf l}[n]$ we have
   $ \Psi_{21}(\alpha)=\sum_{a\models n} c'_a(\alpha) M_a,$
where $a=(2a_1,\ldots,2a_\ell)\models n$ is an integer composition of $n$ with even parts, and $c_a(\alpha)$ is the number of ways to decompose $\alpha$ into $21^*$-subsequences of type $a$.
More precisely
  $$c'_a(\alpha)=\big|\{ A\models [n] :  \text{for } 1\le i\le \ell,\  |A_i|=2a_i \text{ and }st(\alpha|_{A_i})=2143\ldots(2a_i)(2a_i-1)\}\big|.$$
These numbers are new and strange but seem to have interesting properties to study.

The {\sl chromatic} polynomial $\chi^{21}_\alpha(t)$ is then
     $ \chi^{21}_\alpha(t)=\sum_{a\models n} c'_a(\alpha) {t \choose \ell(a)}.$
 This polynomial, when evaluated at $t=m$ counts the number of ways to colors the entries of $\alpha$ with at most $m$ distinct colors such that $\alpha$ restricted to a single color is a $21^*$-sequence.
 Using \cref{thm:AntipodePR} we get the identity
 \begin{equation}
     \sum_{a\models n} (-1)^{\ell(\alpha)}c'_a(\alpha) = (-1)^{n/2} d_{\alpha,2143\ldots(2n)(2n-1)}.
     \end{equation}
\end{example}

\begin{remark} 
The symmetric function $\Psi_{21}(\alpha)$ above is very different from the Stanley chromatic symmetric function for any graph.

\begin{conjecture}  $(-1)^{n/2}\Psi_{21}(\alpha)(-h_1,-h_2,\ldots)$
is $h$-positive.
\end{conjecture}
\end{remark}

%%%%%%%%%%%%%%
%% Future work
%%%%%%%%%%%%%%
\section{Hypergraphical Nestohedron and antipode}\label{ss:nestohedron}

\begin{definition} [Hypergraphical Nestohedron]
 Given a hypergraph $G$ on $V=$\break $\{1,2,\ldots,n\}$,
  the \emph{Hypergraphical Nestohedron} $P_G$ associated to $G$ is the polytope in ${\mathbb R}^n={\mathbb R}\{e_1,e_2,\ldots,e_n\}$
  defined by the Minkowski sum
      $P_G=\sum_{U\in G} {\bf \Delta}_U,$
      where ${\bf \Delta}_U$ is the simplex given by the convex hull of the points $\{e_i : i\in U\}$.
\end{definition}

The acyclic orientations of $G$  label certain {\bf exterior} faces of $P_G$. These orientations encode the coefficients of $S(G)$.

For example, let
$G=
\begin{tikzpicture}[scale=.5,baseline=.3cm]
	\node (1) at (0,.1) {$\scriptstyle 1$};
	\node (2) at (0,1) {$\scriptstyle 3$};
	\node (3) at (1,.5) {$\scriptstyle 2$};
	\draw [fill=blue] (.1,.1) .. controls (.25,.5) .. (.15,.9) .. controls (.4,.5) .. (.85,.5) .. controls (.5,.4) .. (.1,.1) ; 
	\red{\draw (.9,.7).. controls (0.6,1) ..(0.2,1);}
\end{tikzpicture} 
$.
We then have 
$ P_G=\blue{{\bf \Delta}_{123}} + \red{{\bf \Delta}_{23} },
$
where 
\vspace{-3ex}
$$\blue{{\bf \Delta}_{123}} = \begin{tikzpicture}[scale=1.3,baseline=.5cm]
	\node (1) at (0.5,1.0) {
	     $\begin{tikzpicture}[scale=.4,baseline=.5cm]
		\node (1) at (0,.1) {$\scriptstyle 1$};
		\node (2) at (0,1.2) {$\scriptstyle 3$};
		\node (3) at (1,.5) {$\scriptstyle 2$};
		\blue{\draw [->] (.1,.1) .. controls (.25,.5) .. (.15,.9) ; 
		\draw [->] (.1,.1) .. controls (.5,.4) .. (.85,.5) ; }
		\end{tikzpicture} $};
	\node (2) at (-.2,-.2) {
	     $\begin{tikzpicture}[scale=.4,baseline=.5cm]
		\node (1) at (0,.1) {$\scriptstyle 1$};
		\node (2) at (0,1.2) {$\scriptstyle 3$};
		\node (3) at (1,.5) {$\scriptstyle 2$};
		\blue{\draw [->] (.85,.5) .. controls (.4,.5) .. (.15,.9) ; 
		\draw [->] (.85,.5) .. controls (.5,.4) .. (.1,.1) ; }
		\end{tikzpicture} $};
	\node (3) at (1.5,-.2) {
	     $\begin{tikzpicture}[scale=.4,baseline=.5cm]
		\node (1) at (0,.1) {$\scriptstyle 1$};
		\node (2) at (0,1.2) {$\scriptstyle 3$};
		\node (3) at (1,.5) {$\scriptstyle 2$};
		\blue{\draw [->] (.15,.9) .. controls (.4,.5) .. (.85,.5) ; 
		\draw [->] (.15,.9) .. controls (.25,.5) .. (.1,.1) ; }
		\end{tikzpicture} $};
	\node at (1.2,.5) {
	     $\begin{tikzpicture}[scale=.4,baseline=.5cm]
		\node (1) at (0,.5) {$\scriptstyle 13$};
		\node (3) at (1,.5) {$\scriptstyle 2$};
		\blue{\draw [->] (.2,.5) -- (.8,.5) ; }
		\end{tikzpicture} $};
	\node at (.1,.5) {
	     $\begin{tikzpicture}[scale=.4,baseline=.5cm]
		\node (1) at (.5,.1) {$\scriptstyle 12$};
		\node (3) at (.1,1) {$\scriptstyle 3$};
		\blue{\draw [->] (.5,.1) -- (.2,.7) ; }
		\end{tikzpicture} $};
	\node at (.5,-.2) {
	     $\begin{tikzpicture}[scale=.4,baseline=.5cm]
		\node (1) at (0,.1) {$\scriptstyle 1$};
		\node (3) at (.5,1) {$\scriptstyle 23$};
		\blue{\draw [->] (.5,.7) --(.1,.2) ; }
		\end{tikzpicture} $};
	\draw [fill=gray!20!white] (0,0) -- (.6,.75) -- (1.2,0) --(0,0) ; 
	\node at (0.6,.3) {$\scriptstyle 123$};
\end{tikzpicture} \qquad
\red{{\bf \Delta}_{23}} = \begin{tikzpicture}[scale=1.3,baseline=.1cm]
	\node at (-.2,0) {
	     $\begin{tikzpicture}[scale=.4,baseline=.5cm]
		\node (2) at (0,1.2) {$\scriptstyle 3$};
		\node (3) at (1,.5) {$\scriptstyle 2$};
		\red{\draw [->] (.85,.5) .. controls (.55,.8) .. (.15,.9) ; }
		\end{tikzpicture} $};
	\node at (1.5,0) {
	     $\begin{tikzpicture}[scale=.4,baseline=.5cm]
		\node (2) at (0,1.2) {$\scriptstyle 3$};
		\node (3) at (1,.5) {$\scriptstyle 2$};
		\red{\draw [<-] (.85,.5) .. controls (.55,.8) .. (.15,.9) ; }
		\end{tikzpicture} $};
	\draw [thick] (0,0) -- (1.2,0); 
	\node at (.6,.2) {$\scriptstyle 23$};
\end{tikzpicture} 
$$
Here we draw the Minkowski sum of the polytopes above, with the orientation in each face.
\vskip -18pt
$$\begin{tikzpicture}[scale=1.5,baseline=.5cm]
	\node (1) at (0.5,1.0) {
	     $\begin{tikzpicture}[scale=.4,baseline=.5cm]
		\node (1) at (0,.1) {$\scriptstyle 1$};
		\node (2) at (0,1.2) {$\scriptstyle 3$};
		\node (3) at (1,.5) {$\scriptstyle 2$};
		\blue{\draw [->] (.1,.1) .. controls (.25,.5) .. (.15,.9) ; 
		\draw [->] (.1,.1) .. controls (.5,.4) .. (.85,.5) ; }
		\red{\draw [->] (.85,.5) .. controls (.55,.8) .. (.25,.9) ; }
		\end{tikzpicture} $};
	\node  at (2,1.0) {
	     $\begin{tikzpicture}[scale=.4,baseline=.5cm]
		\node (1) at (0,.1) {$\scriptstyle 1$};
		\node (2) at (0,1.2) {$\scriptstyle 3$};
		\node (3) at (1,.5) {$\scriptstyle 2$};
		\blue{\draw [->] (.1,.1) .. controls (.25,.5) .. (.15,.9) ; 
		\draw [->] (.1,.1) .. controls (.5,.4) .. (.85,.5) ; }
		\red{\draw [<-] (.85,.6) .. controls (.55,.8) .. (.15,.9) ; }
		\end{tikzpicture} $};
	\node (2) at (-.2,-.2) {
	     $\begin{tikzpicture}[scale=.4,baseline=.5cm]
		\node (1) at (0,.1) {$\scriptstyle 1$};
		\node (2) at (0,1.2) {$\scriptstyle 3$};
		\node (3) at (1,.5) {$\scriptstyle 2$};
		\blue{\draw [->] (.85,.5) .. controls (.4,.5) .. (.15,.9) ; 
		\draw [->] (.85,.5) .. controls (.5,.4) .. (.1,.1) ; }
		\red{\draw [->] (.85,.5) .. controls (.55,.8) .. (.25,.9) ; }
		\end{tikzpicture} $};
	\node (3) at (2.7,-.2) {
	     $\begin{tikzpicture}[scale=.4,baseline=.5cm]
		\node (1) at (0,.1) {$\scriptstyle 1$};
		\node (2) at (0,1.2) {$\scriptstyle 3$};
		\node (3) at (1,.5) {$\scriptstyle 2$};
		\blue{\draw [->] (.15,.9) .. controls (.4,.5) .. (.85,.5) ; 
		\draw [->] (.15,.9) .. controls (.25,.5) .. (.1,.1) ; }
		\red{\draw [<-] (.85,.6) .. controls (.55,.8) .. (.15,.9) ; }
		\end{tikzpicture} $};
	\node at (2.4,.5) {
	     $\begin{tikzpicture}[scale=.4,baseline=.5cm]
		\node (1) at (0,.5) {$\scriptstyle 13$};
		\node (3) at (1,.5) {$\scriptstyle 2$};
		\blue{\draw [->] (.2,.5) -- (.8,.5) ; }
		\red{\draw [->] (.2,.5) .. controls (.55,.8) .. (.8,.6) ; }
		\end{tikzpicture} $};
	\node at (.1,.5) {
	     $\begin{tikzpicture}[scale=.4,baseline=.5cm]
		\node (1) at (.5,.1) {$\scriptstyle 12$};
		\node (3) at (.1,1) {$\scriptstyle 3$};
		\blue{\draw [->] (.5,.1) -- (.2,.7) ; }
		\red{\draw [->] (.5,.1) .. controls (.5,.6) .. (.3,.7) ; }
		\end{tikzpicture} $};
	\node at (1.2,-.2) {
	     $\begin{tikzpicture}[scale=.4,baseline=.5cm]
		\node (1) at (0,.1) {$\scriptstyle 1$};
		\node (3) at (.5,1) {$\scriptstyle 23$};
		\blue{\draw [->] (.5,.7) --(.1,.2) ; }
		\end{tikzpicture} $};
	\node at (1.2,1) {
	     $\begin{tikzpicture}[scale=.4,baseline=.5cm]
		\node (1) at (0,.1) {$\scriptstyle 1$};
		\node (3) at (.5,1) {$\scriptstyle 23$};
		\blue{\draw [<-] (.5,.7) --(.1,.2) ; }
		\end{tikzpicture} $};
	\draw [fill=gray!10!white] (0,0) -- (.6,.75) -- (1.8,.75) -- (2.4,0) --(0,0) ; 
	\node at (1.2,.35) {$\scriptstyle 123$};
\end{tikzpicture}
$$

The coefficient of the discrete graph is the sum of the six acyclic orientations that
correspond to the three faces on the left and the three faces on the right. We call these exterior faces as no contraction occurs. The total homology is $2$ in this case.
The coefficient $+2$ in $S(G)$ corresponds to the two horizontal faces in the picture (only $\{2,3\}$ is contracted). Finally the coefficient $-1$ corresponds the interior face of the polytope ($\{1,2,3\}$ is contracted). Thus,
  $S(G) = -G + 2(\begin{tikzpicture}[scale=.4,baseline=.1cm]
	\node (1) at (0,.1) {$\scriptstyle 1$};
	\node (2) at (0,1) {$\scriptstyle 3$};
	\node (3) at (1,.5) {$\scriptstyle 2$};
	\draw (.9,.7).. controls (0.6,1) ..(0.2,1);
\end{tikzpicture} ) - 2 (\begin{tikzpicture}[scale=.4,baseline=.1cm]
	\node (1) at (0,.1) {$\scriptstyle 1$};
	\node (2) at (0,1) {$\scriptstyle 3$};
	\node (3) at (1,.5) {$\scriptstyle 2$};
\end{tikzpicture} 
).
$

\printbibliography

\end{document}
